package 算法;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * @author zhangmin
 * @create 2021-12-13 17:49
 */
public class Sort04 {
    /**==============================================================================================================================================
     * JZ3 数组中重复的数字
     * 在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。
     * 1、遍历用set记录
     * 2、排序后判断
     *  */
    public int duplicate (int[] numbers) {
        Arrays.sort(numbers);
        for (int i = 1; i < numbers.length; i++) {
            if (numbers[i] == numbers[i - 1])
                return numbers[i];
        }
        return -1;
    }

    /**==============================================================================================================================================
     * JZ51 数组中的逆序对
     * 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。
     * 分治：使用归并排序思路，当合并两个有序的子数组时，判断前半部分的数值大的话，需要加上前半部分的长度到结果中
     * 进行归并排序时：[l,m],[m+1,r]为两个有序的子数组,i在前半段中，j指向后半段
     * 当i==m+1说明前面半段都拍完了，只需要将后半段中j之后的加入到结果中
     * 当j==r+1 说明后半段排完了，需要将前半段i之后的加入到结果中
     * 当num[i]<=num[j]时，将num[i]加入结果中，i++；
     * 当num[i]>num[j]时，将num[j]加入结果，j++，并且计入m-i+1对逆序对（num[i]后面的到m的元素都比num[j]大，都与num[j]形成逆序对）
     *  */
    int kmod=1000000007;
    int mergeSort(int[] nums,int l,int r){
        if (l>=r) return 0;
        int m=l+(r-l)/2;
        int res=mergeSort(nums,l,m)+mergeSort(nums,m+1,r);
        int i=l,j=m+1;
        //需要一个辅助数组将[l，r]之间的复制出来，这样就在nums原数组上进行merge
        int[] temp=new int[nums.length];
        for (int k = l; k <=r ; k++) {
            temp[k]=nums[k];
        }
        //开始合并，合并结果存放在nums中，在temp中遍历
        for (int k = l; k <=r ; k++) {
            if (i==m+1){
                //i==m+1说明前面半段都拍完了，只需要将后半段中j之后的加入到结果中
                nums[k]=temp[j++];
            }else if (j==r+1){
                //当j==r+1 说明后半段排完了，需要将前半段i之后的加入到结果中
                nums[k]=temp[i++];
            }else if (temp[i]<=temp[j]){
                //当num[i]<=num[j]时，将num[i]加入结果中，i++；
                nums[k]=temp[i++];
            }else if (temp[i]>temp[j]){
                //当num[i]>num[j]时，将num[j]加入结果，j++，并且计入m-i+1对逆序对（num[i]后面的到m的元素都比num[j]大，都与num[j]形成逆序对）
                nums[k]=temp[j++];
                res+=(m-i+1);
                res%=kmod;
            }
        }
        return res;
    }
    public int InversePairs(int [] array) {
        return mergeSort(array,0,array.length-1);
    }

    /**==============================================================================================================================================
     * JZ40 最小的K个数
     * 给定一个长度为 n 的可能有重复值的数组，找出其中不去重的最小的 k 个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4(任意顺序皆可)。
     * 1、排序后取前k个元素
     * 2、快速查找：在划分的时候判断比划分点小的元素的个数，当个数小于k时，接着去后面比划分点大的元素部分划分，直到划分点刚好为k；否则相反
     *  */
    public ArrayList<Integer> GetLeastNumbers_Solution1(int [] input, int k) {
        Arrays.sort(input);
        ArrayList<Integer> res=new ArrayList<>();
        for (int i = 0; i < k; i++) {
            res.add(input[i]);
        }
        return res;
    }

    int partition(int[] input,int l,int r){
        int temp=input[l];
        int i=l+1,j=r;
        while (true){
            //比temp小的在左边，比temp大的在右边
            while (i<=r&&input[i]<temp) i++;
            while (j>=l+1&&input[j]>temp) j--;
            if (i>=j) break;
            //交换
            int t=input[i];
            input[i]=input[j];
            input[j]=t;
        }
        //将temp放到中间位置,此时，j所在的位置为较小元素的最后一个
        input[l]=input[j];
        input[j]=temp;
        return j;
    }
    int[] quickSort(int[] input,int l,int r,int k){
        int p=partition(input,l,r);
        if (p==k) {
            return Arrays.copyOf(input,p+1);
        }
        return p<k?quickSort(input,p+1,r,k):quickSort(input,l,p-1,k);
    }
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        if (k==0||input.length==0) return new ArrayList<>();
        int[] quickSort = quickSort(input, 0, input.length - 1, k - 1);
        ArrayList<Integer> res=new ArrayList<>();
        for (int i = 0; i < quickSort.length; i++) {
            res.add(quickSort[i]);
        }
        return res;
    }

    /**==============================================================================================================================================
     * JZ41 数据流中的中位数
     * 如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。
     * 如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。
     * 用两个堆，一个小顶堆用来存储较大的一半数字，一个大顶堆用来存储较小的一半数字
     * 需要保持两个堆的元素个数差始终不超过1
     *  */
    //small是一个大顶堆，存放较小的一半元素
    PriorityQueue<Integer> small=new PriorityQueue<>(((o1, o2) -> o2-o1));
    //large是一个小顶堆，存储较大的一半元素
    PriorityQueue<Integer> large=new PriorityQueue<>();

    public void Insert(Integer num) {
        if (small.size()>=large.size()){
            //需要向large中添加元素，但是先将元素添加到small中，然后将small中的堆顶元素取出了插入到large
            small.offer(num);
            large.offer(small.poll());
        }else {
            //需要向amsll中添加元素，同样先添加到large中，然后将large的堆顶元素取出放入small中
            large.offer(num);
            small.offer(large.poll());
        }
    }

    public Double GetMedian() {
        //当两个堆元素不相等时，返回数量多的堆的堆顶元素
        if (small.size()==large.size()) return (small.peek()+large.peek())/2.0;
        return Double.valueOf(small.size()>large.size()? small.peek():large.peek());
    }


}
